---
title: "离开中山路"
created: 2025-11-28
tags:
  - 算法
---

# 离开中山路

## 题目 [离开中山路](https://www.luogu.com.cn/problem/P1746)

![[image-619d2fd1.png]]

## 思路分析

给定起点和终点

## 代码实现

0~n-1

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=1010;

char g[N][N];

int d[N][N];

int n;

int x2,y2;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=n-1 && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();

		int ux=cur.first,uy=cur.second;

		q.pop();

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]=='0'){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

	return d[x2][y2];

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=0;i<n;i++)

		cin>>g[i];

//	for(int i=0;i<n;i++){

//		for(int j=0;j<n;j++)

//			cout<<g[i][j]<<" ";

//		cout<<endl;

//	}

	int x,y;

	cin>>x>>y>>x2>>y2;

	x-=1,y-=1,x2-=1,y2-=1;

//	cout<<"x1: "<<x<<" y1: "<<y<<" x2: "<<x2<<" y2: "<<y2<<endl;

	cout<<bfs(x,y)<<endl;

	return 0;

}
```

1~n

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=1010;

char g[N][N];

int d[N][N];

int n;

int x2,y2;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=n && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();

		int ux=cur.first,uy=cur.second;

		q.pop();

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]=='0'){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

	return d[x2][y2];

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++)

		cin>>g[i]+1;

	int x,y;

	cin>>x>>y>>x2>>y2;

	cout<<bfs(x,y)<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[武士风度的牛|武士风度的牛]] 🏠 [[00-刷题理模型]] ➡️ [[走迷宫|走迷宫]]